package aco;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

import aco.Ants.Ant;

public class InsertionHeuristic {

//	插入类
	 static class Insertion {
		 //id of the unrouted customer that should be inserted in a route in the best feasible insertion place
		 int customer;
		 
		 //id of the route or the index of the tour given by the best feasible insertion place
		 int indexTour;
		 
		 //the previous node from the selected tour given by the best feasible insertion place
		 //the unrouted customer will be inserted in the the tour having the index = indexTour and in front
		 //of this node/customer/city
		 int previousNode; // 将城市插入到这个位置。也就是说插入城市后，插入城市在这个城市的前面
		 
		 //computed value for the metric for a certain insertion place, considered when deciding which is the best feasible insertion place
		 //for an unrouted customer
		 double score; // c1的评分
		 
		 public Insertion() {}
		 
		 public Insertion(int customer_, int indexTour_, int previousNode_, double score_) {
			 this.customer = customer_;
			 this.indexTour = indexTour_;
			 this.previousNode = previousNode_;
			 this.score = score_;
		 }

		public int getCustomer() {
			return customer;
		}

		public int getIndexTour() {
			return indexTour;
		}

		public int getPreviousNode() {
			return previousNode;
		}

		public double getScore() {
			return score;
		}
		 
	 }

//	计算蚂蚁a的每条路径中的每个城市的，可接受的，可实现的，最早到达时间，最迟到达时间
	static void computeRouteVariables(Ant a, VRPTW vrp, int startTourIndex) {
		ArrayList<Request> reqList = vrp.getRequests();
		
		//for every customer already included in the solution, compute route variables (earliest time a 
		//delivery can be made at a customer and the latest time a delivery can be made at a customer) 
		//used when checking feasibility of an insertion
		// 计算所得的最迟到达时间和最早到达时间都是可以接受的，不能在时间时间窗范围之外。
		int city, previousCity, nextCity;
		double value, value1, value2;
		
		/*a.earliestTime = new ArrayList(a.usedVehicles);
		a.latestTime = new ArrayList(a.usedVehicles);*/
		
		/*for (int j = 0; j < a.usedVehicles; j++) {
			a.earliestTime.add(j, new ArrayList<Double>());
			a.latestTime.add(j, new ArrayList<Double>());
		}*/

//		1. 计算请求城市集合中，规划好后的，每个城市的最早到达时间（从前往后算）
		//move forward in every tour and compute the values for the earliest time
		for (int index = startTourIndex; index < a.usedVehicles; index++) {
			int tourLength = a.tours.get(index).size();
			//System.out.println("StartTourIndex=" + startTourIndex + " used vehicles=" + a.usedVehicles);
			/*if (a.earliestTime != null) {
				System.out.println("Index=" + index + " length=" + a.earliestTime.size());
			}*/
			if (a.earliestTime == null) {
				System.out.println("Earliest time is null");
			}
			a.earliestTime.add(index, new ArrayList<Double>(tourLength));
			for (int i = 0; i < tourLength; i++) {  // i代表的是城市在路径中的序号，不是城市编号
				city = a.tours.get(index).get(i);  // 当前的城市编号
				//the current city (customer) is the depot
				if (((city + 1) == 0) && (i == 0)) {
					value = new Double(reqList.get(0).getStartWindow());
					a.earliestTime.get(index).add(i, value);
				}
				else {
					previousCity = a.tours.get(index).get(i - 1);  // 前一个城市的编号
					value1 = new Double(reqList.get(city + 1).getStartWindow()); // 当前城市的时间窗开启时间
					//value2 = a.earliestTime.get(index).get(i - 1) + VRPTW.instance.distance[previousCity + 1][city + 1];
					value2 = a.earliestTime.get(index).get(i - 1) + VRPTW.instance.distance[previousCity + 1][city + 1] + reqList.get(previousCity + 1).getServiceTime();
					value = Math.max(value1, value2);
					a.earliestTime.get(index).add(i, value);
				}
			}
		}

//		2. 计算请求城市集合中，已经全都安排好的，最迟到达时间（从后往前算）
		//move backward in every tour and compute the values for the latest time
		for (int index = startTourIndex; index < a.usedVehicles; index++) {
			int tourLength = a.tours.get(index).size();
//			生成一个可变列表，列表长度为tourLength，列表中每个元素的值为0.0
//			因为本段是从后往前数的，所以要提前生成好了这些
			a.latestTime.add(index, new ArrayList<Double>(Collections.nCopies(tourLength, 0.0)));
			for (int i = tourLength - 1; i >= 0; i--) {  // 从后往前数
				city = a.tours.get(index).get(i);  // 当前城市的编号
				if (i == tourLength - 1) {  // 路径末端的城市
					value = new Double(reqList.get(0).getEndWindow()); // 仓库的时间窗结束时间
					value1 = new Double(reqList.get(city + 1).getEndWindow()); // 当前城市的时间窗结束时间
					value2 = value - VRPTW.instance.distance[city + 1][0] - reqList.get(city + 1).getServiceTime();
					value = Math.min(value1, value2);
					a.latestTime.get(index).set(i, value);
				}
				else {
					nextCity = a.tours.get(index).get(i + 1); // 下一个城市编号
					value1 = new Double(reqList.get(city + 1).getEndWindow()); // 下一个城市的最迟到达时间
					//value2 = a.latestTime.get(index).get(i + 1) - VRPTW.instance.distance[city + 1][nextCity + 1];
					value2 = a.latestTime.get(index).get(i + 1) - VRPTW.instance.distance[city + 1][nextCity + 1] - reqList.get(city + 1).getServiceTime();
					value = Math.min(value1, value2);
					a.latestTime.get(index).set(i, value);
				}
			}
		}

	}

//	当插入在当前已有路径中插入新的城市后，更新蚂蚁a每条路径中每个城市的，最早到达时间和最迟到达时间
//	但是没有改变插入城市的最早到达时间和最迟到达时间
//	这是在路径已经插入后的更新
	static void updateRouteVariables(Ant a, VRPTW vrp, Insertion ins) {
		int previousCity, nextCity, bestPos, bestIndexTour;
		double value1, value2, oldLatestTime, newLatestTime, oldEarliestTime, newEarliestTime;
		
		ArrayList<Request> reqList = vrp.getRequests();
		bestIndexTour = ins.getIndexTour(); // 插入路径
		bestPos = ins.getPreviousNode(); // 插入城市的位置

//		更新插入城市之前城市序列的最迟到达时间
		for (int k = bestPos - 1; k >= 0; k--) {
			previousCity = a.tours.get(bestIndexTour).get(k); // 插入城市前面城市的编号
			nextCity = a.tours.get(bestIndexTour).get(k + 1); // 插入城市的编号
			// 因为是倒着计算，插入城市位置后的序列不变，前面的城市序列向前移一位。
			oldLatestTime = a.latestTime.get(bestIndexTour).get(k);
			value1 = a.latestTime.get(bestIndexTour).get(k + 1)  // 插入城市的最迟到达时间
					- VRPTW.instance.distance[previousCity + 1][nextCity + 1] // 距离时间
					- reqList.get(previousCity + 1).getServiceTime(); // 插入城市前面城市的服务时间
			newLatestTime = Math.min(oldLatestTime, value1);
			if (oldLatestTime != newLatestTime) {
				a.latestTime.get(bestIndexTour).set(k, newLatestTime);
			}
			else{
				break;
			}	
		}

//		更新插入城市之后城市序列的最早到达时间
		for (int k = bestPos + 1; k < a.tours.get(bestIndexTour).size(); k++) {
			previousCity = a.tours.get(bestIndexTour).get(k - 1); // 插入城市的位置
			nextCity = a.tours.get(bestIndexTour).get(k); // 插入城市后面城市的位置
			// 插入城市操作前，这个位置的城市的最早开始时间，为旧的最早到达时间
			oldEarliestTime = a.earliestTime.get(bestIndexTour).get(k);
			value2 = a.earliestTime.get(bestIndexTour).get(k - 1)  // 插入城市的最早到达时间
					+ VRPTW.instance.distance[previousCity + 1][nextCity + 1] // 路上时间
					+ reqList.get(previousCity + 1).getServiceTime(); // 插入城市的服务时间
			newEarliestTime = Math.max(oldEarliestTime, value2); 
			if (oldEarliestTime != newEarliestTime) {
				a.earliestTime.get(bestIndexTour).set(k, newEarliestTime);
			}
			else {
				break;
			}
		}
		
	}

//	判断路径indexTour，是否可行，主要是判断“载量”和“时间”。
//	将编号为customer的城市插入到路径的nextPos位置
//	这个方法好像没有用到
	static boolean checkIsFeasibleTour(Ant a, VRPTW vrp, int customer, int indexTour, int previousPos, int nextPos) {
		boolean res = true;
		int currentCity, prevCity;
		double currentQuantity, currentTime;
		double distance, arrivalTime, beginService;
		ArrayList<Request> reqList = vrp.getRequests();

//		1. 从仓库出发的路径载量和当前时间
		currentQuantity = reqList.get(0).getDemand(); // 初始载量为仓库的需求量
		currentTime = 0.0; // 初始时间为在仓库的时间

//		2. 第一个城市到nextPos-1的位置，计算当前时间和载量，判断时间窗约束
		for (int currentPos = 1; currentPos < nextPos; currentPos++) {
			prevCity = a.tours.get(indexTour).get(currentPos - 1);
			currentCity = a.tours.get(indexTour).get(currentPos);
			currentQuantity += reqList.get(currentCity + 1).getDemand();
			
			distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
	    	arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance; 
	    	beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
	    	if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
	    		//isFeasible = false;
	    		return false;
	    	}
	    	currentTime = beginService;
		}

//		3. nextPos位置插入城市，计算当前时间和载量，判断时间窗约束
		//currentQuantity = a.currentQuantity.get(indexTour);
		prevCity = a.tours.get(indexTour).get(nextPos - 1);
		currentCity = customer;
		currentQuantity += reqList.get(currentCity + 1).getDemand();
	    //currentTime = a.beginService[prevCity + 1];
		
		distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
    	arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance; 
    	beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
    	if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
    		//isFeasible = false;
    		return false;
    	}
    	currentTime = beginService;

//		4. nextPos+1位置，计算当前时间和载量，判断时间窗约束
    	prevCity = customer;
		currentCity = a.tours.get(indexTour).get(nextPos);
		currentQuantity += reqList.get(currentCity + 1).getDemand();
		
		distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
    	arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance; 
    	beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
    	if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
    		//isFeasible = false;
    		return false;
    	}
    	currentTime = beginService;

//		5. nextPos+1到路径末尾，计算当前时间和载量，判断时间窗约束
    	for (int currentPos = nextPos + 1; currentPos < a.tours.get(indexTour).size(); currentPos++) {
			prevCity = a.tours.get(indexTour).get(currentPos - 1);
			currentCity = a.tours.get(indexTour).get(currentPos);
			currentQuantity += reqList.get(currentCity + 1).getDemand();
			
			distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
	    	arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance; 
	    	beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
	    	if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
	    		//isFeasible = false;
	    		return false;
	    	}
	    	currentTime = beginService;	
		}

//		6. 判断载量约束
		if (currentQuantity > vrp.getCapacity()) {
			//isFeasible = false;
			return false;
		}
		
		return res;
	}

//	判断，将编号为customer的城市插入到路径indexTour中，插入到previousPos后面，nextPos前面
	//check if it is feasible to insert the client denoted by customer, in the tour designated by 
	//indexTour; the customer is checked if it can be inserted between the nodes at position previousPos and nextPos 
	static boolean isFeasibleInsertion(Ant a, VRPTW vrp, int customer, int indexTour, int previousPos, int nextPos) {
		boolean isFeasible1 = false, isFeasible2 = false;
		double currentQuantity, arrivalTime, arrivalTime1, beginService, earliestTime, latestTime;
		double value1, value2, value3, value4;
    	ArrayList<Request> reqList = vrp.getRequests();
    	
    	int previousCity = a.tours.get(indexTour).get(previousPos);
        int nextCity = a.tours.get(indexTour).get(nextPos);
    	currentQuantity = a.currentQuantity.get(indexTour) + reqList.get(customer + 1).getDemand();
    	arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][customer + 1]; 
    	beginService = Math.max(arrivalTime, reqList.get(customer + 1).getStartWindow());
    	value1 = new Double(reqList.get(customer + 1).getStartWindow());
    	//value2 = a.earliestTime.get(indexTour).get(previousPos) + VRPTW.instance.distance[previousCity + 1][customer + 1];
    	value2 = a.earliestTime.get(indexTour).get(previousPos) + VRPTW.instance.distance[previousCity + 1][customer + 1] + reqList.get(previousCity + 1).getServiceTime();
    	earliestTime = Math.max(value1, value2);
    	value3 = new Double(reqList.get(customer + 1).getEndWindow());
    	//value4 = a.latestTime.get(indexTour).get(nextPos) - VRPTW.instance.distance[customer + 1][nextCity + 1];
    	value4 = a.latestTime.get(indexTour).get(nextPos) - VRPTW.instance.distance[customer + 1][nextCity + 1] - reqList.get(customer + 1).getServiceTime();
    	latestTime = Math.min(value3, value4);
    	//arrivalTime1 = beginService + reqList.get(customer + 1).getServiceTime() + VRPTW.instance.distance[customer + 1][nextCity + 1];
    	
		if ((currentQuantity <= vrp.getCapacity()) && (earliestTime <= latestTime) && (beginService <= reqList.get(customer + 1).getEndWindow())) {
				//&& (arrivalTime1 <= a.latestTime.get(indexTour).get(previousPos)))	{
			isFeasible1 = true;
		}
		
		/*if (isFeasible1) {
			isFeasible2 = checkIsFeasibleTour(a, vrp, customer, indexTour, previousPos, nextPos);
			if (isFeasible2 == false) {
				System.out.println("Some inconsistency in checking for feasibility");
			}
		}*/
		
		return isFeasible1;
		
		/*isFeasible2 = checkIsFeasibleTour(a, vrp, customer, indexTour, previousPos, nextPos);
		return isFeasible2;*/
	}

	/**
	 * 插入启发式方法，将节点插入到已有路径的城市与城市之间
	 *	计算C1，得到每个未访问城市的Insertion类集合；
	 *	计算C2，从所有未访问城市的Insertion类集合中找出最优的对象，执行插入操作。
	 * @param a
	 * @param vrp
	 * @param unvisitedNodes：未访问的城市集合
	 * @param startIndexTour：开始遍历的路径编号
	 * @param startPos：每条路径的开始位置的集合。大小应该是a.usedVehicles
	 */
	static void insertUnroutedCustomers(Ant a, VRPTW vrp, ArrayList<Integer> unvisitedNodes, int startIndexTour, ArrayList<Integer> startPos) {
		boolean ok = true;
		double c11, c12, c13, c1, c1_, c2, value1, value2, value3, value4, earliestTime, latestTime;
		double bestC1Score = Double.MAX_VALUE;
		double bestC2Score = Double.MAX_VALUE;
		double arrivalTime, beginService = 0.0, newArrivalTime, newBeginService, oldBeginService, newQuantity, newDistance;
		int previousCity, nextCity, bestPos = 1, bestCustomer, bestIndexTour = 0, bestIndexInsertion = 0;
		int cust;
		double mu = 1.0, alfa1 = 0.1, alfa2 = 0.9, alfa3 = 0.2, lambda = 2.0;  //alfa1 = 0.1, alfa2 = 0.9
		ArrayList<Request> reqList = vrp.getRequests();
		Insertion ins, bestInsertion;
		int startIndex = 0;

		// 未指定路径的客户，最佳的插入位置的集合，最佳插入的集合
		//it contains for each unrouted customer its best feasible insertion place
		//this list is used when deciding the best unrouted customer to be inserted in the unfeasible solution 
		ArrayList<Insertion> bestInsertions = new ArrayList<Insertion>();

		// visited<城市编号, 是否被访问>
		//keep track of nodes (customers) inserted/included in the solution by the insertion heuristic 
		HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>(unvisitedNodes.size());
		for (int node: unvisitedNodes) {
			visited.put(node, false);
		}

		// 计算从路径startIndexTour开始的，每条路径中每个城市节点的，最早到达时间和最迟到达时间
	    computeRouteVariables(a, vrp, startIndexTour);
		
		while (ok) { // 尽量将所有可插入的城市，插入到已有的路径中
			if (bestInsertions != null && bestInsertions.size() > 0) {
				bestInsertions.clear();
			}
			// Find the best possible feasible position to insert an unrouted customer into a tour, then insert it and update the score
//			1. 遍历每个未访问的城市，customer为城市编号（为customer城市寻找最佳的插入路径的最佳插入位置，也就是通过C1计算bestInsertions）
			for (int customer : unvisitedNodes) {
				//check if the customer was not included/inserted in the solution in the meantime by the insertion heuristic
				if (!visited.get(customer)) {  
					bestC1Score = Double.MAX_VALUE;
					for (int indexTour = startIndexTour; indexTour < a.usedVehicles; indexTour++) {
						if (indexTour > startPos.size() - 1) {
							startIndex = 1;
						}
						else {
							startIndex = startPos.get(indexTour) + 1;
						}
						//check for a feasible insertion place within the considered tour
						for (int pos = startIndex; pos < a.tours.get(indexTour).size(); pos++) {
							if (isFeasibleInsertion(a, vrp, customer, indexTour, pos - 1, pos)) {
								//compute the score (value) for the c1 metric
								previousCity = a.tours.get(indexTour).get(pos - 1);
								nextCity = a.tours.get(indexTour).get(pos);
								c11 = VRPTW.instance.distance[previousCity + 1][customer + 1] + VRPTW.instance.distance[customer + 1][nextCity + 1] - mu * VRPTW.instance.distance[previousCity + 1][nextCity + 1];
								arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][customer + 1]; 
						    	beginService = Math.max(arrivalTime, reqList.get(customer + 1).getStartWindow());
								newArrivalTime = beginService + reqList.get(customer + 1).getServiceTime() + VRPTW.instance.distance[customer + 1][nextCity + 1]; 
								newBeginService = Math.max(newArrivalTime, reqList.get(nextCity + 1).getStartWindow());		
								oldBeginService = a.beginService[nextCity + 1];
						    	c12 = newBeginService - oldBeginService;
						    	c13 = reqList.get(customer + 1).getEndWindow() - beginService;
								//c1 = alfa1 * c11 + alfa2 * c12 + alfa3 * c13;
								c1 = alfa1 * c11 + alfa2 * c12;
								if (c1 < bestC1Score) {
									bestC1Score = c1;
									bestIndexTour = indexTour;
									bestPos = pos;
								}
							}
						}
					}
					//we have a best feasible insertion position for the unrouted node denoted by "customer"
					if (bestC1Score != Double.MAX_VALUE) {
						ins = new Insertion(customer, bestIndexTour, bestPos, bestC1Score);
						bestInsertions.add(ins);
					}
				}
				
			}

//			2. 通过计算并比较C2的值，找到bestInsetions集合中的最佳Insertion
			bestC2Score = Double.MAX_VALUE;
			Insertion insert;
			//decide the best customer to be inserted in the solution
			if (bestInsertions != null && bestInsertions.size() > 0) {
				for (int i = 0; i < bestInsertions.size(); i++) {
					insert = bestInsertions.get(i);
					cust = insert.getCustomer();
					c1_= insert.getScore();
					c2 = lambda * VRPTW.instance.distance[0][cust + 1] - c1_;
					//c2 = c1_;
					if (c2 < bestC2Score) {
						bestC2Score = c2;
						bestIndexInsertion = i;
					}
				}
			}

//			3. 如果找到了最佳的Insertion，则将customer城市插入到路径
			//we have the best customer to be inserted in the solution, now we should perform the insertion
			//of the selected best customer
			if (bestC2Score != Double.MAX_VALUE) {
				bestInsertion = bestInsertions.get(bestIndexInsertion);
				bestCustomer = bestInsertion.getCustomer();
				bestIndexTour = bestInsertion.getIndexTour();
				bestPos = bestInsertion.getPreviousNode();

//				3.1 更改蚂蚁类中的一些变量值
				//System.out.println("Inserting unrouted customer " + bestCustomer + " in tour " + (bestIndexTour + 1) + " before node at position " + bestPos);
				a.tours.get(bestIndexTour).add(bestPos, bestCustomer);
				a.visited[bestCustomer] = true;
				a.toVisit--;
				newQuantity = a.currentQuantity.get(bestIndexTour) + reqList.get(bestCustomer + 1).getDemand();
				a.currentQuantity.set(bestIndexTour, newQuantity);
				visited.put(bestCustomer, true);

//				3.2 更新更新插入城市的最早到达时间和最迟到达时间
				//update earliest time and latest time lists to include the value for the newly inserted customer
				previousCity = a.tours.get(bestIndexTour).get(bestPos - 1);
				nextCity = a.tours.get(bestIndexTour).get(bestPos + 1);
		    	value1 = new Double(reqList.get(bestCustomer + 1).getStartWindow());
		    	//value2 = a.earliestTime.get(bestIndexTour).get(bestPos - 1) + VRPTW.instance.distance[previousCity + 1][bestCustomer + 1];
		    	value2 = a.earliestTime.get(bestIndexTour).get(bestPos - 1) + VRPTW.instance.distance[previousCity + 1][bestCustomer + 1] + reqList.get(previousCity + 1).getServiceTime();
		    	earliestTime = Math.max(value1, value2);
		    	value3 = new Double(reqList.get(bestCustomer + 1).getEndWindow());
		    	//value4 = a.latestTime.get(bestIndexTour).get(bestPos) - VRPTW.instance.distance[bestCustomer + 1][nextCity + 1];
		    	value4 = a.latestTime.get(bestIndexTour).get(bestPos) - VRPTW.instance.distance[bestCustomer + 1][nextCity + 1] - reqList.get(bestCustomer + 1).getServiceTime();
		    	latestTime = Math.min(value3, value4); 
		    	a.earliestTime.get(bestIndexTour).add(bestPos, earliestTime);
		    	a.latestTime.get(bestIndexTour).add(bestPos, latestTime);

//		    	3.3 更新插入城市。序列之前城市的最迟到达时间，序列之后城市的最早到达时间
				updateRouteVariables(a, vrp, bestInsertion);

//				3.4 每个城市的到达时间，每条路径的末端城市的到达时间
				//update the begin service times for the nodes that come after the inserted customer on the route
				//also update the begin service time for the inserted node itself
				for (int j = bestPos; j < a.tours.get(bestIndexTour).size(); j++) {
					previousCity = a.tours.get(bestIndexTour).get(j - 1);
					cust = a.tours.get(bestIndexTour).get(j);
					arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][cust + 1]; 
			    	beginService = Math.max(arrivalTime, reqList.get(cust + 1).getStartWindow());
			    	a.beginService[cust + 1] = beginService;
				}
				a.currentTime.set(bestIndexTour, beginService);
				ok = true;
			}
			else {
				// 如果不能找打任何一个未访问城市可以执行插入操作，则跳出循环
				//System.out.println("No feasible insertion position was found; no unrouted customer could be inserted in the solution");
				ok = false;
			}
		}
	}
}
